\select@language {english}
\select@language {brazil}
\select@language {brazil}
\select@language {english}
\contentsline {chapter}{List of Figures}{vii}
\contentsline {chapter}{List of Tables}{x}
\contentsline {chapter}{Abbreviations and Symbols}{xiii}
\contentsline {chapter}{\numberline {1}Introduction}{5}
\contentsline {section}{\numberline {1.1}Overview}{5}
\contentsline {section}{\numberline {1.2}Motivations}{6}
\contentsline {section}{\numberline {1.3}Contributions}{7}
\contentsline {section}{\numberline {1.4}Outline of the chapters}{9}
\contentsline {chapter}{\numberline {2}Statistical learning}{11}
\contentsline {section}{\numberline {2.1}Introduction}{11}
\contentsline {section}{\numberline {2.2}Machine learning}{11}
\contentsline {section}{\numberline {2.3}Learning process}{13}
\contentsline {section}{\numberline {2.4}Risk functional}{13}
\contentsline {section}{\numberline {2.5}Empirical risk minimization principle}{15}
\contentsline {section}{\numberline {2.6}VC dimension}{17}
\contentsline {section}{\numberline {2.7}Structural risk minimization principle}{18}
\contentsline {section}{\numberline {2.8}Conclusion}{20}
\contentsline {chapter}{\numberline {3}Support Vector Machines}{21}
\contentsline {section}{\numberline {3.1}Introduction}{21}
\contentsline {section}{\numberline {3.2}SVMs with hard margins}{22}
\contentsline {section}{\numberline {3.3}SVMs with soft margins}{24}
\contentsline {section}{\numberline {3.4}Implicit mapping using kernel functions}{27}
\contentsline {section}{\numberline {3.5}An example}{29}
\contentsline {section}{\numberline {3.6}Conclusion}{30}
\contentsline {chapter}{\numberline {4}Training SVMs}{31}
\contentsline {section}{\numberline {4.1}Introduction}{31}
\contentsline {section}{\numberline {4.2}Optimality conditions and feasible regions}{32}
\contentsline {section}{\numberline {4.3}Training methods for SVMs}{33}
\contentsline {subsection}{\numberline {4.3.1}Classical methods}{33}
\contentsline {subsection}{\numberline {4.3.2}Geometric methods}{34}
\contentsline {subsection}{\numberline {4.3.3}Iterative methods}{35}
\contentsline {subsubsection}{\numberline {4.3.3.1}Gradient ascent}{35}
\contentsline {subsubsection}{\numberline {4.3.3.2}Successive Over Relaxation}{38}
\contentsline {subsection}{\numberline {4.3.4}Working set methods}{42}
\contentsline {subsubsection}{\numberline {4.3.4.1}QP sub-problem}{42}
\contentsline {subsubsection}{\numberline {4.3.4.2}Chunking}{44}
\contentsline {subsubsection}{\numberline {4.3.4.3}$\mathrm {SVM}^{light}${}}{44}
\contentsline {subsubsection}{\numberline {4.3.4.4}Sequential Minimal Optimization}{45}
\contentsline {section}{\numberline {4.4}Conclusion}{52}
\contentsline {chapter}{\numberline {5}The SVM-KM training strategy}{53}
\contentsline {section}{\numberline {5.1}Introduction}{53}
\contentsline {section}{\numberline {5.2}$k$-means}{55}
\contentsline {section}{\numberline {5.3}Clustering and boundaries}{57}
\contentsline {subsection}{\numberline {5.3.1}Modeling the boundary estimation process}{58}
\contentsline {subsubsection}{\numberline {5.3.1.1}A hypothetical example}{61}
\contentsline {subsection}{\numberline {5.3.2}A measure for boundary estimation by $k$-means}{63}
\contentsline {subsection}{\numberline {5.3.3}Generalization and performance analysis}{68}
\contentsline {subsection}{\numberline {5.3.4}Proposed strategies}{85}
\contentsline {section}{\numberline {5.4}Simulations}{87}
\contentsline {section}{\numberline {5.5}Discussion}{89}
\contentsline {subsection}{\numberline {5.5.1}KM initialization time and KM time}{89}
\contentsline {subsection}{\numberline {5.5.2}SVM time, training set size and SV}{90}
\contentsline {subsection}{\numberline {5.5.3}Generalization and total time}{91}
\contentsline {section}{\numberline {5.6}Conclusion}{92}
\contentsline {chapter}{\numberline {6}The SVM-EDR training algorithm}{103}
\contentsline {section}{\numberline {6.1}Introduction}{103}
\contentsline {section}{\numberline {6.2}Boosting}{104}
\contentsline {subsection}{\numberline {6.2.1}AdaBoost algorithm}{106}
\contentsline {section}{\numberline {6.3}The SVM-EDR training algorithm}{108}
\contentsline {subsection}{\numberline {6.3.1}Error Dependent Repetition}{109}
\contentsline {subsection}{\numberline {6.3.2}EDR for SVMs}{110}
\contentsline {subsection}{\numberline {6.3.3}Understanding and estimating $n_E$}{112}
\contentsline {subsubsection}{\numberline {6.3.3.1}Example 1}{112}
\contentsline {subsubsection}{\numberline {6.3.3.2}Example 2}{115}
\contentsline {subsubsection}{\numberline {6.3.3.3}Virtual training set}{117}
\contentsline {subsection}{\numberline {6.3.4}SVM-EDR as a Boosting algorithm}{117}
\contentsline {subsubsection}{\numberline {6.3.4.1}SVMs output as a sum of weak hypothesis}{119}
\contentsline {subsubsection}{\numberline {6.3.4.2}Error distribution probability convergence}{120}
\contentsline {subsection}{\numberline {6.3.5}Algorithm details}{122}
\contentsline {section}{\numberline {6.4}Simulation}{123}
\contentsline {subsection}{\numberline {6.4.1}First experiment}{124}
\contentsline {subsection}{\numberline {6.4.2}Second experiment}{124}
\contentsline {subsection}{\numberline {6.4.3}Third experiment}{126}
\contentsline {section}{\numberline {6.5}Discussions}{126}
\contentsline {subsection}{\numberline {6.5.1}Separation hyperplanes}{126}
\contentsline {subsection}{\numberline {6.5.2}Convergence}{127}
\contentsline {subsection}{\numberline {6.5.3}Training time}{128}
\contentsline {subsection}{\numberline {6.5.4}Number of iterations and Z set size}{128}
\contentsline {subsection}{\numberline {6.5.5}Generalization and number of support vectors}{129}
\contentsline {section}{\numberline {6.6}Conclusion}{129}
\contentsline {chapter}{\numberline {7}Conclusions and future works}{143}
\contentsline {section}{\numberline {7.1}Introduction}{143}
\contentsline {section}{\numberline {7.2}The SVM-KM training strategy}{143}
\contentsline {subsection}{\numberline {7.2.1}Boundary estimation by $k$-means}{144}
\contentsline {subsection}{\numberline {7.2.2}Speeding up KM}{146}
\contentsline {subsection}{\numberline {7.2.3}Generalization and performance analysis}{147}
\contentsline {subsection}{\numberline {7.2.4}Performance of the proposed strategies}{147}
\contentsline {section}{\numberline {7.3}The SVM-EDR training algorithm}{149}
\contentsline {subsection}{\numberline {7.3.1}SVM-EDR implementation}{149}
\contentsline {subsection}{\numberline {7.3.2}Virtual training set and Boosting}{150}
\contentsline {subsection}{\numberline {7.3.3}Convergence of SVM-EDR}{151}
\contentsline {subsection}{\numberline {7.3.4}Separation hyperplanes}{152}
\contentsline {subsection}{\numberline {7.3.5}Training time}{152}
\contentsline {subsection}{\numberline {7.3.6}Number of iterations and Z set size}{153}
\contentsline {subsection}{\numberline {7.3.7}Generalization and number of support vectors}{153}
\contentsline {section}{\numberline {7.4}Future works}{154}
\contentsline {chapter}{Bibliography}{157}
\contentsline {chapter}{\numberline {A}SVMBR program overview}{169}
\contentsline {section}{\numberline {A.1}Introduction}{169}
\contentsline {section}{\numberline {A.2}Internal structure}{169}
\contentsline {section}{\numberline {A.3}Using SVMBR}{170}
\contentsline {section}{\numberline {A.4}SVMBR use summary}{174}
\contentsfinish 
